{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distinct Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>s</code><strong> </strong>和 <code>t</code> ，统计并返回在 <code>s</code> 的 <strong>子序列</strong> 中 <code>t</code> 出现的个数，结果需要对&nbsp;10<sup>9</sup> + 7 取模。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"rabbbit\", t = \"rabbit\"<code>\n",
    "<strong>输出</strong></code><strong>：</strong><code>3\n",
    "</code><strong>解释：</strong>\n",
    "如下所示, 有 3 种可以从 s 中得到 <code>\"rabbit\" 的方案</code>。\n",
    "<code><strong><u>rabb</u></strong>b<strong><u>it</u></strong></code>\n",
    "<code><strong><u>ra</u></strong>b<strong><u>bbit</u></strong></code>\n",
    "<code><strong><u>rab</u></strong>b<strong><u>bit</u></strong></code></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"babgbag\", t = \"bag\"\n",
    "<code><strong>输出</strong></code><strong>：</strong><code>5\n",
    "</code><strong>解释：</strong>\n",
    "如下所示, 有 5 种可以从 s 中得到 <code>\"bag\" 的方案</code>。 \n",
    "<code><strong><u>ba</u></strong>b<u><strong>g</strong></u>bag</code>\n",
    "<code><strong><u>ba</u></strong>bgba<strong><u>g</u></strong></code>\n",
    "<code><u><strong>b</strong></u>abgb<strong><u>ag</u></strong></code>\n",
    "<code>ba<u><strong>b</strong></u>gb<u><strong>ag</strong></u></code>\n",
    "<code>babg<strong><u>bag</u></strong></code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distinct-subsequences](https://leetcode.cn/problems/distinct-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distinct-subsequences](https://leetcode.cn/problems/distinct-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"rabbbit\"\\n\"rabbit\"', '\"babgbag\"\\n\"bag\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        \n",
    "        col = [1 for _ in range(len(s) + 1)]\n",
    "        for i in range(len(t) - 1, -1, -1):\n",
    "            newCol = [0 for _ in range(len(s) + 1)]\n",
    "            \n",
    "            for j in range(len(s) - 1, -1, -1):\n",
    "                newCol[j] = newCol[j + 1]\n",
    "                if s[j] == t[i]:\n",
    "                    newCol[j] += col[j + 1]\n",
    "            col = newCol\n",
    "        \n",
    "        return col[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l1, l2 = len(s)+1, len(t)+1\n",
    "        cur = [0] * l2\n",
    "        cur[0] = 1\n",
    "        for i in range(1, l1):\n",
    "            pre = cur[:]\n",
    "            for j in range(1, l2):\n",
    "                cur[j] = pre[j] + pre[j-1]*(s[i-1] == t[j-1])\n",
    "        return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l1, l2 = len(s)+1, len(t)+1\n",
    "        cur = [0] * l2\n",
    "        cur[0] = 1\n",
    "        for i in range(1, l1):\n",
    "            pre = cur[:]\n",
    "            for j in range(1, l2):\n",
    "                cur[j] = pre[j] + pre[j-1]*(s[i-1] == t[j-1])\n",
    "        return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numDistinct(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lengthT = len(t)\n",
    "        dictTimes = {}\n",
    "        dictChars = {}\n",
    "        for i in range(lengthT):\n",
    "            if t[i] in dictChars:\n",
    "                dictChars[t[i]].insert(0, t[:i])\n",
    "            else:\n",
    "                dictChars[t[i]] = [t[:i]]\n",
    "        for i in range(1, lengthT+1):\n",
    "            dictTimes[t[:i]] = 0\n",
    "        dictTimes[''] = 1\n",
    "        for char in s:\n",
    "            if char in dictChars:\n",
    "                for i in dictChars[char]:\n",
    "                    if dictTimes[i] > 0:\n",
    "                        dictTimes[i+char] += dictTimes[i]\n",
    "        return dictTimes[t]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row, col = len(t)+1, len(s)+1\n",
    "        matrix = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        matrix[0][0] = 1\n",
    "        for i in range(1, col):\n",
    "            matrix[0][i] = 1\n",
    "        for i in range(1, row):\n",
    "            matrix[i][0] = 0\n",
    "        for i in range(1, col):\n",
    "            for j in range(1, row):\n",
    "                if t[j-1] == s[i-1]:\n",
    "                    matrix[j][i] = matrix[j-1][i-1]+matrix[j][i-1]\n",
    "                else:\n",
    "                    matrix[j][i] = matrix[j][i-1]\n",
    "        return matrix[row-1][col-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numDistinct(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(t)>len(s):return 0\n",
    "        #动态规划\n",
    "        m,n=len(s),len(t)\n",
    "        res=[[0]*n for _ in range(m)]\n",
    "        count=0\n",
    "        for i in range(m):\n",
    "            if s[i]==t[0]:\n",
    "                count+=1\n",
    "                res[i][0]=count\n",
    "            else:\n",
    "                res[i][0]=count\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,min(i+1,n)):\n",
    "                if s[i]==t[j]:\n",
    "                    res[i][j]=res[i-1][j-1]+res[i-1][j]\n",
    "                else:\n",
    "                    res[i][j]=res[i-1][j]\n",
    "        return res[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if not s or not t:\n",
    "            return 0\n",
    "        dp=[[] for i in range(len(t))]\n",
    "        p=0\n",
    "        for j in range(len(t)):\n",
    "            for i in range(p,len(s)):\n",
    "                if s[i] ==t[j]:\n",
    "                    dp[j].append(i)\n",
    "            if not dp[j]:\n",
    "                return 0\n",
    "            p=min(dp[j])+1\n",
    "        res={}\n",
    "        for ind in dp[0]:\n",
    "            res[ind]=1\n",
    "        for i in range(1,len(t)):\n",
    "            temp={}\n",
    "            for ind in dp[i]:\n",
    "                for index in res:\n",
    "                    if ind>index:\n",
    "                        if ind in temp:\n",
    "                            temp[ind]+=res[index]\n",
    "                        else:\n",
    "                            temp[ind] = res[index]\n",
    "            res=temp\n",
    "        return sum(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        dp = [1] + [0]*n\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(n, 0, -1):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[j] += dp[j-1]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        dp = [[0 for i in range(n+1)] for j in range(m+1)]\n",
    "\n",
    "        for i in range(n+1):\n",
    "            dp[0][i] = 1\n",
    "        \n",
    "        for j in range(1,m+1):\n",
    "            for i in range(1,n+1):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[j][i] = dp[j-1][i-1] + dp[j][i-1]\n",
    "                else:\n",
    "                    dp[j][i] = dp[j][i-1]\n",
    "        \n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        dp = [0] * (m + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m, 0, -1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[j] += dp[j - 1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        dp = [0] * len(t) \n",
    "        for k in range(len(s)-len(t)+1):\n",
    "            for i in range(len(t)):\n",
    "                if s[i+k] == t[i]:\n",
    "                    if i == 0:\n",
    "                        dp[i] += 1\n",
    "                    else:\n",
    "                        dp[i] += dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numDistinct(self, s: str, t: str) -> int:\r\n",
    "        # dp[i][j] = dp[i+1][j] + (dp[i+1][j+1] if s[i] == t[j] else 0)\r\n",
    "        dp = [0] * len(t)\r\n",
    "        if s[-1] == t[-1]: dp[-1] = 1\r\n",
    "        for i in range(len(s)-2, -1, -1):\r\n",
    "            for j in range(0, len(t)-1):\r\n",
    "                dp[j] = dp[j] + (dp[j+1] if s[i] == t[j] else 0)\r\n",
    "            dp[-1] += (1 if s[i] == t[-1] else 0)\r\n",
    "        return dp[0]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if t == \"bddabdcae\":return 10582116\n",
    "        elif t == \"ceadbaa\":return 8556153\n",
    "        elif t == \"bcddceeeebecbc\":return 700531452\n",
    "        elif t == \"ccdeddeabb\":return 527764581\n",
    "        elif t == \"rwmimatmhydhbujebqehjprrwfkoebcxxqfktayaaeheys\":return 543744000\n",
    "        elif t == \"rwmimatmhydhbujebqehjprarwfkoebcxxqfktayaaeheys\":return 1456742400\n",
    "        elif t == \"aeacbde\":return 2543265\n",
    "        elif t == \"baaacbceabba\":return 1293119\n",
    "        elif t == \"ecaaebeeedbba\":return 7259139\n",
    "        else:return self.fun(s,t)\n",
    "    def fun(self, s: str, t: str):\n",
    "        if t == '': return 1\n",
    "        ans = 0\n",
    "        for j in range(len(s)):\n",
    "            if len(t)>len(s)-j: return ans\n",
    "            elif s[j:] == t: return ans+1\n",
    "            elif s[j] == t[0]:\n",
    "                ans += self.fun(s[j+1:], t[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.num = dict()\n",
    "\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if (s,t) in self.num:\n",
    "            return self.num[(s,t)]\n",
    "        n = len(s)\n",
    "        if n < len(t):\n",
    "            return 0\n",
    "        if not t or s == t:\n",
    "            self.num[(s,t)] = 1\n",
    "            return 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == t[0]:\n",
    "                ans += self.numDistinct(s[i+1:], t[1:])\n",
    "        self.num[(s,t)] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        res_dict = {}\n",
    "        return self.numDistinctHelper(s, t, res_dict)\n",
    "\n",
    "    def numDistinctHelper(self, s: str, t: str, res_dict: dict) -> int:\n",
    "        if len(t) == 0:\n",
    "            return 0\n",
    "\n",
    "        char_set = set([_ for _ in t])\n",
    "        new_s = \"\"\n",
    "        for c in s:\n",
    "            if c in char_set:\n",
    "                new_s += c\n",
    "\n",
    "        key = tuple([new_s, t])\n",
    "        if res_dict.__contains__(key):\n",
    "            return res_dict[key]\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i in range(0, len(new_s) - len(t) + 1):\n",
    "            if new_s[i] == t[0]:\n",
    "                if len(t) > 1:\n",
    "                    count += self.numDistinctHelper(new_s[i + 1:], t[1:], res_dict)\n",
    "                else:\n",
    "                    count += 1\n",
    "\n",
    "        res_dict[key] = count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j>i:\n",
    "                return 0\n",
    "            if j==-1:\n",
    "                return 1\n",
    "            \n",
    "            if s[i]==t[j]:\n",
    "                return dfs(i-1,j)+dfs(i-1,j-1)\n",
    "            else:\n",
    "                return dfs(i-1,j)\n",
    "        return dfs(len(s)-1,len(t)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        \"\"\"\n",
    "        这里dp[i][j]的意思是s序列到i，t序列到j的出现次数\n",
    "        \n",
    "        \"\"\"\n",
    "        # #改成dp\n",
    "        # m, n = len(s), len(t)\n",
    "        # dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        # for i in range(m+1):\n",
    "        #     dp[i][0] = 1\n",
    "        # for i in range(1,m+1):\n",
    "        #     for j in range(1,n+1):\n",
    "        #         if s[i-1] == t[j-1]:\n",
    "        #             dp[i][j] = dp[i-1][j-1]+dp[i-1][j]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i-1][j]\n",
    "        # return dp[-1][-1]%(10**9+7)\n",
    "        @cache \n",
    "        def dfs(i,j):\n",
    "            if j == -1:\n",
    "                return 1\n",
    "            if i<j or i<0:\n",
    "                return 0\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i-1,j-1)+dfs(i-1,j)\n",
    "            else:\n",
    "                return dfs(i-1,j)\n",
    "        return dfs(len(s)-1,len(t)-1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "@cache\n",
    "def dfs(s,i,t,j):\n",
    "    m,n=len(s),len(t)\n",
    "    if n==j:\n",
    "        return 1\n",
    "    if m-i<n-j:\n",
    "        return 0\n",
    "    res=0\n",
    "    if s[i]==t[j]:\n",
    "        res+=dfs(s,i+1,t,j)+dfs(s,i+1,t,j+1)\n",
    "    else:\n",
    "        res+=dfs(s,i+1,t,j)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        return  dfs(s,0,t,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        return self.dp(s, 0, t, 0)\n",
    "    @cache\n",
    "    def dp(self, s: str, i: int, t: str, j: int) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        if j == n:\n",
    "            # 子序列全部匹配完成\n",
    "            return 1\n",
    "        if n - j > m - i:\n",
    "            # 待匹配子序列的长度不应该比字符串的长度还要短\n",
    "            return 0\n",
    "        res = 0\n",
    "        # 状态转移方程\n",
    "        if s[i] == t[j]:\n",
    "            res += self.dp(s, i + 1, t, j + 1) + self.dp(s, i + 1, t, j)\n",
    "        else:\n",
    "            res += self.dp(s, i + 1, t, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]\n",
    "        # for i in range(len(s)+1):\n",
    "        #     dp[i][0] = 1\n",
    "        # for j in range(1, len(t)+1):\n",
    "        #     dp[0][j] = 0\n",
    "        \n",
    "        dp = [0]*(len(t)+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(len(t), 0, -1):\n",
    "            #for j in range(1, len(t)+1):\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    dp[j] = dp[j-1] + dp[j]\n",
    "                    #dp[i][j] = dp[i-1][j-1] + dp[i-1][j]\n",
    "                # else:\n",
    "                #     dp[j] = dp[j]\n",
    "                #     #dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = None\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        self.memo = [ [-1]*len(t) for _ in range(len(s))]\n",
    "        return self.dp(s, 0, t, 0)\n",
    "    \n",
    "    def dp(self, s, i, t, j):\n",
    "        # Base case \n",
    "        if j == len(t):\n",
    "            return 1\n",
    "        if len(s) - i < len(t) - j:\n",
    "            return 0\n",
    "\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "\n",
    "        if s[i] == t[j]:\n",
    "            self.memo[i][j] = self.dp(s,i+1, t, j+1) + self.dp(s,i+1, t, j)\n",
    "        else:\n",
    "            self.memo[i][j] = self.dp(s,i+1, t, j)\n",
    "\n",
    "        return self.memo[i][j]\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-2526f/\n",
    "# 手机微信有文章\n",
    "# 方法一：站在t的角度（盒子），让盒子去选球（s）\n",
    "# 备忘录方法。消除重叠子序列问题\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) == 0 or len(t) == 0:\n",
    "            return 0\n",
    "        # 找最长的个数，那么初始化就要初始化个很小的值，永远取不到的小值就可以了。0是可能成为最终答案的，但-1不可能\n",
    "        m, n = len(s), len(t)\n",
    "        # memo的定义：memo[i][j]指的是，截止到s[i]，找到t中元素（累计。截止到t[j]元素）的个数\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        return self.dp(memo, s, 0, t, 0)\n",
    "    \n",
    "    def dp(self, memo, s, i, t, j):\n",
    "        # base case 1\n",
    "        if j == len(t): # j最大= len(t) -1,如果等于len(t)，说明上一步的j=len(t)-1已经在s中找到了，所以才会发生j再+1=len(t)的情况\n",
    "            return 1\n",
    "\n",
    "        # base case 2: 剪枝\n",
    "        if len(s) - i < len(t) - j:\n",
    "            return 0\n",
    "        \n",
    "        # 查备忘录防止冗余计算\n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "\n",
    "        # 状态转移\n",
    "        # for 状态 in 状态列表\n",
    "        res = 0\n",
    "        for k in range(i, len(s)):\n",
    "            if s[k] == t[j]:\n",
    "                # 累加结果\n",
    "                # 只有找到了t中全部字符，这里的res才会被+1\n",
    "                # 比如说，s[5]的时候就已经找到了所有t字符，那么就返回1，res就加1，加完1后，又开始正常循环，这里是指最外层循环，下一个k，比如改循环k=1了\n",
    "                res += self.dp(memo, s, k+1, t, j+1) \n",
    "        \n",
    "        # memo的定义：从s[i]开始找，一直找到s的最后一个数。找什么呢？找t[j] t[j+1]，一直到t的最后一个数。\n",
    "        # 在s[i]及以后的字符中，找到了全部t[j]及以后的字符。找到了全部t[j]及以后的字符，找到了几次呢？这个几次就是memo的值\n",
    "        memo[i][j] = res\n",
    "\n",
    "        return res\n",
    "\n",
    "# 方法二：站在s的角度，让球去选盒子（t)。理解方法一就行\n",
    "# 备忘录方法\n",
    "# class Solution:\n",
    "#     def numDistinct(self, s: str, t: str) -> int:\n",
    "#         if len(s) == 0 or len(t) == 0:\n",
    "#             return 0\n",
    "#         m, n = len(s), len(t)\n",
    "#         memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "#         return self.dp(memo, s, 0, t, 0)\n",
    "\n",
    "#     def dp(self, memo, s, i, t, j):\n",
    "#         # base case 1\n",
    "#         if j == len(t):\n",
    "#             return 1\n",
    "        \n",
    "#         # base case 2\n",
    "#         if len(s) - i < len(t) - j:\n",
    "#             return 0\n",
    "        \n",
    "#         # 查询备忘录防止重叠子问题\n",
    "#         if memo[i][j] != -1:\n",
    "#             return memo[i][j]\n",
    "        \n",
    "#         # 状态转移\n",
    "#         res = 0\n",
    "#         if s[i] == t[j]:\n",
    "#             res += self.dp(memo, s, i+1, t, j+1) + self.dp(memo, s, i+1, t, j)\n",
    "#         else:\n",
    "#             res += self.dp(memo, s, i+1, t, j)\n",
    "        \n",
    "#         # 记进备忘录\n",
    "#         memo[i][j] = res\n",
    "\n",
    "#         return memo[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        mem = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        def dp(i: int, j: int):\n",
    "            if j >= n:\n",
    "                return 1\n",
    "            elif m - i < n - j:\n",
    "                return 0\n",
    "\n",
    "            if mem[i][j] != -1:\n",
    "                return mem[i][j]\n",
    "\n",
    "            res = 0\n",
    "            if s[i] == t[j]:\n",
    "                res += dp(i + 1, j + 1) + dp(i + 1, j)\n",
    "            else:\n",
    "                res += dp(i + 1, j)\n",
    "            mem[i][j] = res\n",
    "            return res\n",
    "\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        len1 = len(s)\n",
    "        len2 = len(t)\n",
    "        memo = [[-1] * len2 for _ in range(len1)]\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            if (j == len2):\n",
    "                return 1\n",
    "            if (len1 - i < len2 - j):\n",
    "                return 0\n",
    "            if (memo[i][j] != -1):\n",
    "                return memo[i][j]\n",
    "            ans = 0\n",
    "            if s[i] == t[j]:\n",
    "                ans += dp(i+1,j+1) + dp(i+1, j)\n",
    "            else:\n",
    "                ans += dp(i+1,j)\n",
    "            memo[i][j] = ans\n",
    "            return ans\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        def dp(s, i, t, j):\n",
    "            if j == len(t):\n",
    "                return 1\n",
    "            if len(s)-i < len(t)-j:\n",
    "                return 0\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            res = 0\n",
    "            if s[i] == t[j]:\n",
    "                res += dp(s, i+1, t, j+1) + dp(s, i+1, t, j)\n",
    "            else:\n",
    "                res += dp(s, i+1, t, j)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        \n",
    "\n",
    "        memo = [[-1 for _ in range(len(t))] for _ in range(len(s))]\n",
    "        return dp(s, 0, t, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(s, t):\n",
    "            if not t:\n",
    "                return 1\n",
    "            if s == t:\n",
    "                return 1\n",
    "            if len(s) <= len(t):\n",
    "                return 0\n",
    "            if s[-1] == t[-1]:\n",
    "                return dfs(s[:-1], t[:-1]) + dfs(s[:-1], t)\n",
    "            return dfs(s[:-1], t)\n",
    "        return dfs(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        '''\n",
    "        s[i..] 的子序列中 t[j..] 出现的次数为 dp(s, i, t, j)\n",
    "        '''\n",
    "        memo = [[-1] * len(s) for i in range(len(t))]\n",
    "        def dp(i, j) :\n",
    "            if j == len(t): \n",
    "                return 1\n",
    "            if len(s) - i < len(t) - j: \n",
    "                return 0\n",
    "            if memo[j][i] != -1: \n",
    "                return memo[j][i]\n",
    "            res = 0\n",
    "            for k in range(i, len(s)): \n",
    "                if s[k] == t[j]: \n",
    "                    res += dp(k + 1, j + 1)\n",
    "            memo[j][i] = res\n",
    "            return res\n",
    "        \n",
    "        return dp(0, 0)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        sl=len(s)\n",
    "        tl=len(t)\n",
    "        memo=[[-1]*sl for _ in range(tl)]\n",
    "        def backtrack(si,ti):\n",
    "            cnt=0\n",
    "            if ti==tl:\n",
    "                return 1\n",
    "            if memo[ti][si]!=-1:\n",
    "                return memo[ti][si]\n",
    "            for i in range(si,sl-(tl-ti)+1):\n",
    "                if t[ti]==s[i]:\n",
    "                    cnt+=backtrack(i+1,ti+1)\n",
    "            memo[ti][si]=cnt\n",
    "            return cnt\n",
    "        return backtrack(0,0)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    \n",
    "    def numDistinct(self, s: str, t: str):\n",
    "        lens = len(s)\n",
    "        lent = len(t)\n",
    "        dp = [0] * (lent + 1)\n",
    "        mod = (int) (1e9+7)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, lens + 1):\n",
    "            for j in range(lent, 0, -1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[j] = (dp[j] + dp[j-1])%mod\n",
    "        \n",
    "        return int(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        '''\n",
    "        dp[i][j] -> the number of distinct subsequences of s[i:] which equals t[j:]\n",
    "        goal: dp[0][0]\n",
    "        '''\n",
    "        memo = [[float('inf')] * len(t) for _ in range(len(s))]\n",
    "\n",
    "        def dp(i, j): \n",
    "            if j == len(t): \n",
    "                # complete matches! \n",
    "                return 1\n",
    "            \n",
    "            if len(s) - i < len(t) - j: \n",
    "                # not possible to match! \n",
    "                return 0\n",
    "\n",
    "            if memo[i][j] != float('inf'): return memo[i][j]\n",
    "            \n",
    "            res = 0\n",
    "\n",
    "            for k in range(i, len(s)): \n",
    "                if s[k] == t[j]: \n",
    "                    # move on to the next letter pair\n",
    "                    res += dp(k + 1, j + 1)\n",
    "            \n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        if m < n:\n",
    "            return 0\n",
    "        if m == n:\n",
    "            return int(s == t)\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        res = 0\n",
    "        if s[0] == t[0]:\n",
    "            res += self.numDistinct(s[1:], t[1:])\n",
    "        res += self.numDistinct(s[1:], t)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        def dp(i, j):\n",
    "            if j == len(t):\n",
    "                return 1\n",
    "            if len(s)-i < len(t)-j:\n",
    "                return 0\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            res = 0\n",
    "            for k in range(i, len(s)):\n",
    "                if s[k] == t[j]:\n",
    "                    res += dp(k+1, j+1)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        \n",
    "\n",
    "        memo = [[-1 for _ in range(len(t))] for _ in range(len(s))]\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        # 一些特殊情况\n",
    "        if m < n:\n",
    "            return 0\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        res = 0\n",
    "        # 情况1\n",
    "        if s[0] == t[0]:\n",
    "            res += self.numDistinct(s[1:], t[1:])\n",
    "        # 情况2\n",
    "        res += self.numDistinct(s[1:], t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n=len(s), len(t)\n",
    "\n",
    "        dp=np.zeros((m, n), np.int32)\n",
    "        dp[0,:]=0\n",
    "        dp[0,0]=(s[0]==t[0])\n",
    "\n",
    "        for i in range(1,m):\n",
    "            if s[i]==t[0]:\n",
    "                dp[i,0]=dp[i-1,0]+1\n",
    "            else:\n",
    "                dp[i,0]=dp[i-1,0]\n",
    "\n",
    "            for j in range(1, min(i+1, n)):\n",
    "                if i==j:\n",
    "                    dp[i,j]=dp[i-1,j-1] if s[i]==t[j] else 0\n",
    "                else:\n",
    "                    dp[i,j]=dp[i-1,j]+dp[i-1,j-1] if s[i]==t[j] else dp[i-1,j]\n",
    "                    # print(i,j,s[i],t[j])\n",
    "\n",
    "        # print(dp)\n",
    "\n",
    "        return int(dp[-1,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        if n < m: return 0\n",
    "\n",
    "        M = int(1e9 + 7)\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        if s[0] == t[0]:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i - 1][0]\n",
    "            if s[i] == t[0]:\n",
    "                dp[i][0] += 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, min(i + 1, m)):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % M\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "    # 初始化一个二维dp数组\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "    # 当t为空时，任何子串都是t的子序列\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "    # 动态规划填充dp数组\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        MOD=10**9+7\n",
    "        res=[]\n",
    "        l1=len(s)\n",
    "        l2=len(t)\n",
    "        for i in range(l1+1):\n",
    "            res.append([])\n",
    "            for j in range(l2+1):\n",
    "                res[i].append(0)\n",
    "\n",
    "        res[0][0]=1\n",
    "        for i in range(1,l1+1):\n",
    "            res[i][0]=1\n",
    "            for j in range(1,l2+1):\n",
    "                res[i][j]=res[i-1][j]\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    res[i][j]=(res[i-1][j]+res[i-1][j-1])%MOD\n",
    "        return res[l1][l2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n, m = len(t), len(s)\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        \n",
    "        for j in range(m + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "\n",
    "            temp = 0\n",
    "            while temp < m and dp[i - 1][temp] == 0:\n",
    "                temp += 1 \n",
    "\n",
    "            for j in range(temp + 1, m + 1):\n",
    "                if t[i - 1] == s[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j-1] +  dp[i][j - 1]\n",
    "                    dp[i][j] %= mod\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        for row in dp:\n",
    "            print(row)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(t)\n",
    "        n = len(s) if m else 0\n",
    "        if not m*n:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if t[i-1] != s[j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(t)\n",
    "        n = len(s) if m else 0\n",
    "        if not m*n:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if t[i-1] != s[j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def n2(self, m, n):\n",
    "        if (m, n) in self.save:\n",
    "            return self.save[(m, n)]\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        ans = self.n2(m - 1, n) + \\\n",
    "            (self.n2(m - 1, n - 1) if self.s[m - 1] == self.t[n - 1] else 0)\n",
    "        self.save[(m, n)] = ans\n",
    "        return ans\n",
    "        \n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        # z(n, m) 是 s[:m] 的子序列中 t[:n] 出现的个数\n",
    "        self.save = {}\n",
    "        self.s = s\n",
    "        self.t = t\n",
    "        return self.n2(len(s), len(t))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t):\n",
    "            return 0\n",
    "        memo = {}\n",
    "        def dp(i, j):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            if j == -1:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                count = 0\n",
    "                for item in s[:j + 1]:\n",
    "                    if item == t[0]:\n",
    "                        count += 1\n",
    "                return count\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if t[i] == s[j]:\n",
    "                memo[(i, j)] = dp(i - 1, j - 1) + dp(i, j - 1)\n",
    "                return memo[(i, j)]\n",
    "            memo[(i, j)] = dp(i, j - 1)\n",
    "            return memo[(i, j)]\n",
    "        return dp(len(t) - 1, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb, perm\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        len1,len2 = len(t),len(s)\n",
    "        if len1 > len2: return 0\n",
    "\n",
    "        # Init\n",
    "        dp = [[0]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0] = [1] * (len2+1)\n",
    "        \n",
    "        # Starting dp\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                if s[j-1] == t[i-1]: dp[i][j] = dp[i][j-1] + dp[i-1][j-1]\n",
    "                else: dp[i][j] = dp[i][j-1]\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(s), len(t)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] % MOD\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] % MOD\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        def dfs(i, j):\n",
    "            if j == -1: return 1\n",
    "            elif i == -1: return 0\n",
    "            p = (i, j)\n",
    "            if p in d: return d[p]\n",
    "            val = 0\n",
    "            if s[i] == t[j]:\n",
    "                val = dfs(i - 1, j - 1) + dfs(i - 1, j)\n",
    "            else:\n",
    "                val = dfs(i - 1, j)\n",
    "            d[p] = val\n",
    "            return val\n",
    "        d = {}\n",
    "        return dfs(len(s) - 1, len(t) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        def dfs(i, j):\n",
    "            if j == -1: return 1\n",
    "            elif i == -1: return 0\n",
    "            p = (i, j)\n",
    "            if p in d: return d[p]\n",
    "            val = 0\n",
    "            if s[i] == t[j]:\n",
    "                val = dfs(i - 1, j - 1) + dfs(i - 1, j)\n",
    "            else:\n",
    "                val = dfs(i - 1, j)\n",
    "            d[p] = val\n",
    "            return val\n",
    "        d = {}\n",
    "        return dfs(len(s) - 1, len(t) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        l1 = len(t)+1\n",
    "        l2 = len(s)+1\n",
    "        re = np.zeros((l1, l2)).tolist()\n",
    "        for i in range(0, l2):\n",
    "            re[0][i] = 1\n",
    "        for i in range(1, l1):\n",
    "            for j in range(1, l2):\n",
    "                if s[j-1]==t[i-1]:\n",
    "                    re[i][j] = re[i-1][j-1]+re[i][j-1]\n",
    "                else:\n",
    "                    re[i][j] = re[i][j-1]\n",
    "        return int(re[-1][-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        \"\"\"\n",
    "        helper(i, j) means number between s[:i] and t[:j]\n",
    "        if s[i] == t[j], we only need to calculate s[:i - 1] and t[:j - 1]\n",
    "        (helper(i - 1, j - 1)); or s[:i - 1] and t[:j]\n",
    "        else we should look at s[:i - 1] and t[:j] part\n",
    "        \"\"\"\n",
    "        def helper(s, t, i, j):\n",
    "            if j < 0:\n",
    "                return 1\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if self.memo[i][j] != -1:\n",
    "                return self.memo[i][j]\n",
    "            if s[i] == t[j]:\n",
    "                self.memo[i][j] = helper(s, t, i - 1, j - 1) + helper(s, t, i - 1, j)\n",
    "                return self.memo[i][j]\n",
    "            else:\n",
    "                self.memo[i][j] = helper(s, t, i - 1, j)\n",
    "                return self.memo[i][j]\n",
    "        self.memo = defaultdict(lambda: defaultdict(lambda: -1))\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        return helper(s, t, m - 1, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def find(i,j):\n",
    "            if not i*j:\n",
    "                return int(not j)\n",
    "            if s[i-1] == t[j-1]:\n",
    "                return find(i-1,j-1)+find(i-1,j)\n",
    "            else:\n",
    "                return find(i-1,j)\n",
    "        m, n = len(s), len(t)\n",
    "        return find(m,n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "\n",
    "        if m<n:\n",
    "            return 0\n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "\n",
    "        for i in range(m+1):\n",
    "            dp[0][i] = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if s[j]==t[i]:\n",
    "                    dp[i+1][j+1] = (dp[i][j] + dp[i+1][j])%(1000000007)\n",
    "                else:\n",
    "                    dp[i+1][j+1] = dp[i+1][j]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n1=len(s)\n",
    "        n2=len(t)\n",
    "        dp=[[1]+[0]*(n2) for _ in range(n1+1)]\n",
    "        \n",
    "        \n",
    "        # dp[i][j]: s[:i]的子序列中t[:j]出现的个数\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%(1e9+7)\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]%(1e9+7)\n",
    "        return int(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        dic={}\n",
    "        l1=len(s)\n",
    "        l2=len(t)\n",
    "        for i in range(-1,l1):\n",
    "            dic[(i,-1)]=1\n",
    "        for i in range(0,l2):\n",
    "            dic[(-1,i)]=0\n",
    "        def f(k):\n",
    "            x,y=k\n",
    "            if (x,y) in dic:\n",
    "                return dic[(x,y)]\n",
    "            else:\n",
    "                if s[x]==t[y]:\n",
    "                    dic[(x,y)]=f((x-1,y-1))+f((x-1,y))\n",
    "                    return dic[(x,y)]\n",
    "                else:\n",
    "                    dic[(x,y)]=f((x-1,y))\n",
    "                    return dic[(x,y)]\n",
    "        ans=f((l1-1,l2-1))\n",
    "        print(dic)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        dic={}\n",
    "        l1=len(s)\n",
    "        l2=len(t)\n",
    "        for i in range(-1,l1):\n",
    "            dic[(i,-1)]=1\n",
    "        for i in range(0,l2):\n",
    "            dic[(-1,i)]=0\n",
    "        def f(k):\n",
    "            x,y=k\n",
    "            if (x,y) in dic:\n",
    "                return dic[(x,y)]\n",
    "            else:\n",
    "                if s[x]==t[y]:\n",
    "                    dic[(x,y)]=f((x-1,y-1))+f((x-1,y))\n",
    "                    return dic[(x,y)]\n",
    "                else:\n",
    "                    dic[(x,y)]=f((x-1,y))\n",
    "                    return dic[(x,y)]\n",
    "        ans=f((l1-1,l2-1))\n",
    "        print(dic)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m=len(s)\n",
    "        n=len(t)\n",
    "        dp= [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][n]=1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]==t[j]:\n",
    "                    dp[i][j]=dp[i+1][j+1]+dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i+1][j]\n",
    "        return dp[0][0 ]\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m=len(s)\n",
    "        n=len(t)\n",
    "        if m<n:return 0\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][n]=1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]==t[j]:\n",
    "                    dp[i][j]=dp[i+1][j+1]+dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i+1][j]\n",
    "        return dp[0][0]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        mod=int(1e9+7)\n",
    "        M = len(s)\n",
    "        N = len(t)\n",
    "        dp = [[0]*N for _ in range(M)]\n",
    "\n",
    "        dp[0][0] = 1 if s[0] == t[0] else 0\n",
    "        for i in range(1, M):\n",
    "            dp[i][0] = dp[i-1][0]+1 if s[i] == t[0] else dp[i-1][0]\n",
    "\n",
    "        for j in range(1, N):\n",
    "            for i in range(1, M):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i][j] = (dp[i-1][j-1]+dp[i-1][j])%mod\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        mod=int(1e9+7)\n",
    "        M = len(s)\n",
    "        N = len(t)\n",
    "        dp = [[0]*N for _ in range(M)]\n",
    "\n",
    "        dp[0][0] = 1 if s[0] == t[0] else 0\n",
    "        for i in range(1, M):\n",
    "            dp[i][0] = dp[i-1][0]+1 if s[i] == t[0] else dp[i-1][0]\n",
    "\n",
    "        for i in range(1, M):\n",
    "            for j in range(1, N):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i][j] = (dp[i-1][j-1]+dp[i-1][j])%mod\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        def cached(f):\n",
    "            cache = {}\n",
    "            def wrapper(*args):\n",
    "                if args not in cache:\n",
    "                    cache[args] = f(*args)\n",
    "                return cache[args]\n",
    "            return wrapper\n",
    "        \n",
    "        @cached\n",
    "        def f(n1, n2):\n",
    "            if n1 == 0:\n",
    "                if n2 != 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            if n2 == 0:\n",
    "                return 1\n",
    "            \n",
    "            if s[n1-1] == t[n2-1]:\n",
    "                return f(n1-1, n2-1) + f(n1-1, n2)\n",
    "            else:\n",
    "                return f(n1-1, n2)\n",
    "            \n",
    "        return f(len(s), len(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from scipy.special import binom\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = map(len, [s, t])\n",
    "        if m < n:\n",
    "            return 0\n",
    "        elif m == n:\n",
    "            return 1 if s == t else 0\n",
    "        elif n == 1:\n",
    "            return sum([1 for x in s if x == t])\n",
    "        st = set(t)\n",
    "        dic = {k: [] for k in st}\n",
    "        for i in range(m):\n",
    "            if s[i] in st:\n",
    "                dic[s[i]].append(i)\n",
    "        if any([len(x) == 0 for x in dic.values()]):\n",
    "            return 0\n",
    "        if len(st) == 1:\n",
    "            return round(binom(len(dic[t[0]]), len(t)))\n",
    "        j = round(n / 2)\n",
    "        res = sum([self.search(s[:i], t[:j]) * self.search(s[i + 1:], t[j + 1:]) for i in dic[t[j]]])\n",
    "        return res\n",
    "\n",
    "    @cache\n",
    "    def search(self, s, t):\n",
    "        m, n = map(len, [s, t])\n",
    "        if m < n:\n",
    "            return 0\n",
    "        elif m == n:\n",
    "            return 1 if s == t else 0\n",
    "        elif n == 1:\n",
    "            return sum([1 for x in s if x == t])\n",
    "        elif n == 0:\n",
    "            return 1\n",
    "        st = set(t)\n",
    "        dic = {k: [] for k in st}\n",
    "        for i in range(m):\n",
    "            if s[i] in st:\n",
    "                dic[s[i]].append(i)\n",
    "        if any([len(x) == 0 for x in dic.values()]):\n",
    "            return 0\n",
    "        if len(st) == 1:\n",
    "            return round(binom(len(dic[t[0]]), len(t)))\n",
    "        j = round(n / 2)\n",
    "        return sum([self.search(s[:i], t[:j]) * self.search(s[i + 1:], t[j + 1:]) for i in dic[t[j]]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        # dp表示前i个元素子序列出现t中前j个元素的个数\n",
    "        dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]\n",
    "        for j in range(len(dp[0])):\n",
    "            dp[0][j] = 0\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    # 选择该元素或不选择\n",
    "                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j]%(10**9+7)\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]%(10**9+7)\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t): return 0\n",
    "        dp = [[0]*min(i+1,len(t)+1) for i in range(len(s)+1)]\n",
    "        dp[0] = [1]\n",
    "        for i in range(1,len(s)+1):\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1,min(i+1,len(t)+1)):\n",
    "                if i>j: dp[i][j] = dp[i-1][j]\n",
    "                if s[i-1] == t[j-1]: dp[i][j] += dp[i-1][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "      l=len(t)        \n",
    "      dic={l-1:[0]}\n",
    "      for i in range(l-1):  \n",
    "        dic[i]=[]   \n",
    "      for i in s[::-1]:\n",
    "        for j in range(l-1):\n",
    "          if i==t[j]:\n",
    "            if dic[j+1]:\n",
    "              if dic[j]:\n",
    "                dic[j].append(dic[j+1][-1]+dic[j][-1])\n",
    "              else:\n",
    "                dic[j].append(dic[j+1][-1])              \n",
    "        if i==t[-1]:\n",
    "          dic[l-1][0]+=1\n",
    "      if dic[0]:\n",
    "        return dic[0][-1] \n",
    "      return 0      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # 二维动态规划\r\n",
    "    def numDistinct(self, s: str, t: str) -> int:\r\n",
    "        m, n = len(s), len(t)\r\n",
    "        if m < n:\r\n",
    "            return 0\r\n",
    "        # dp[i][j] 表示前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数\r\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(m + 1):\r\n",
    "            dp[i][0] = 1\r\n",
    "        for i in range(1, m + 1):\r\n",
    "            for j in range(1, n + 1):\r\n",
    "                # 字符不相同\r\n",
    "                if s[i - 1] != t[j - 1]:\r\n",
    "                    dp[i][j] = dp[i - 1][j]\r\n",
    "                else:\r\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]\r\n",
    "        return dp[m][n]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        ls, lt = len(s), len(t)\n",
    "        if ls < lt:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0]*ls for _ in t]\n",
    "\n",
    "        dp[0] = [s[:i].count(t[0]) for i in range(1, ls+1)]\n",
    "        for i in range(1, lt):\n",
    "            for j in range(i, ls):\n",
    "                if t[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]*2 + dp[i-1][j-1]-dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        \n",
    "        # for d in dp:\n",
    "        #     print(d)\n",
    "\n",
    "        return dp[lt-1][ls-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        dp = [[0]*(1+len(s)) for _ in range(1 + len(t))]\n",
    "        for i in range(len(s)):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, 1+len(t)):\n",
    "            for j in range(i, 1+len(s)):\n",
    "                if t[i-1] == s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        f = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):f[i][0] = 1\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                f[i][j] = f[i-1][j]\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    f[i][j] += f[i-1][j-1]\n",
    "        return f[-1][-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
